#coding=utf-8 
'''
Created on 2012-10-25

@author: infear
'''
#http://blog.csdn.net/v_JULY_v/article/details/6057286
#46.搜狐（运算）：
#四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
import LinkedNode

def func(num,state=()):
    left=state.count('<')
    right=state.count('>')
    if left==num:
        if right!=num:
            for result in func(num,state+('>',)):
                yield ('>',)+result
        else:
            yield ()
    else:
        for result in func(num,state+('<',)):
            yield ('<',)+result;
        if left!=right:
            for result in func(num,state+('>',)):
                yield ('>',)+result


#48.微软（运算）：
#一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}
#是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
def searchNumInArr(num,arr):
    list_num=list(str(num))
    for i in range(0,len(list_num)):
        list_num[i]=int(list_num[i])
    i=0
    while i!=len(arr)-1:
        if list_num[i]<list_num[i+1]:
            break;
        i=i+1
    if i==len(arr)-1:
        return False;
    for j in range(0,i+1):
        if arr[j+i-1]!=list_num[j]:
            return False
    for j in range(i+1,len(arr)):
        if list_num[j]!=arr[j-i-1]:
            return False
    return True


#58.从尾到头输出链表（链表）。
#题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。
def reversePrint(head):
    if head:
        reversePrint(head.next)
        print head.value

#61.找出数组中两个只出现一次的数字（数组）
#题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
#请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
#这个题目考察位运算很多 
def findNumAppearOnce(arr):
    tmp_1=0
    for i in arr:
        tmp_1=tmp_1^i
    tmp_2=1
    while tmp_1!=1:
        tmp_1=tmp_1>>1
        tmp_2=tmp_2<<1
    group1=group2=0
    for i in arr:
        if i&tmp_2==tmp_2:
            group1=group1^i
        else:
            group2=group2^i
    return group1,group2

       
#62.找出链表的第一个公共结点（链表）。
#题目：两个单向链表，找出它们的第一个公共结点。        
def findFirstCommonNodeInNotCycleList(h1,h2):
    if h1 is None or h2 is None:
        return None
    p1,p2=h1,h2
    l1=l2=0
    while p1.next:
        p1=p1.next
        l1=l1+1
    while p2.next:
        p2=p2.next
        l2=l2+1
    if p1!=p2:
        return None
    p1,p2=h1,h2
    if l1>l2:
        gap=l1-l2
        while gap!=0:
            p1=p1.next
            gap=gap-1
        while p1!=p2:
            p1=p1.next
            p2=p2.next
        return p1
    else:
        gap=l2-l1
        while gap!=0:
            l2=l2.next()
            gap=gap-1
        while p1!=p2:
            p1=p1.next
            p2=p2.next
        return p2
    
#63.在字符串中删除特定的字符（字符串）。
#题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
#例如，输入”They are students.”和”aeiou”，
#则删除之后的第一个字符串变成”Thy r stdnts.”。
def deleteChar(source,charSet):
    p='['+charSet+']'
    print p
    import re
    return re.sub(pattern=p, repl="", string=source)

#64. 寻找丑数（运算）。
#题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，
#但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
#求按从小到大的顺序的第1500个丑数。
def findUnlyNum(count):
    ele=(1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27)
    index=count/len(ele)
    offset=count%len(ele)
    if offset!=0:
        return pow(30, index)*ele[offset-1]
    else:
        return pow(30,index)

#65.输出1到最大的N位数（运算）
#题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，
#则输出1、2、3一直到最大的3位数即999。
#注意这里不能用整型
def outputMaxNDigits(N):
    import re 
    if N==0:
        yield "" 
    else:
        for result in outputMaxNDigits(N-1):
            for i in range(0,10):
                #这里要注意如果递归的结果都是0的话，那么只需要生成自己就可以了
                if result!="" and re.search(r'[1-9]',result) is not None:
                    yield result+str(i)
                else:
                    yield str(i)

#66.颠倒栈（栈）。
#题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
#颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。
def reverseStack(l1,l2=[]):
    if len(l1)==0:
        for i in l2:
            l1.append(i)
    else:
        l2.append(l1.pop())
        reverseStack(l1,l2)
            
#68.把数组排成最小的数（数组、算法）。
#题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
#例如输入数组{32,  321}，则输出这两个能排成的最小数字32132。
#请给出解决问题的算法，并证明该算法。        
#用上字符串比较很容易    
def generateMinInteger(arr,tag=True):
    if len(arr)==0:
        return ""
    if tag:
        for i in range(0,len(arr)):
            arr[i]=str(arr[i])
    min=arr[0]
    index=0
    for i in range(0,len(arr)):
        if arr[i]<min:
            min=arr[i]
            index=i
    return min+generateMinInteger(arr[:index]+arr[index+1:],False)

#71.数值的整数次方（数字、运算）。
#题目：实现函数double Power(double base, int exponent)，求base的exponent次方。
#不需要考虑溢出。
def exponent(base,ex):
    if ex==1:
        return base
    else:
        temp=exponent(base,ex/2)
        if ex&1==1:  
            return base*temp*temp
        else:
            return temp*temp

#73.对称字符串的最大长度（字符串）。
#题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
#比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
#从中心开始比较的思想很关键 
#特别注意从中心扩展的 两种情况一种是aba,abba
def maxMirrorSubStringLength(_str):
    if _str is None or len(_str)==0:
        return 0
    str_list=list(_str)
    l=len(str_list)
    index=0
    max_length=1
    max_index=0
    while index!=l:
        index_start=index_end=index
        while index_start!=0 and index_end!=l and str_list[index_start]==str_list[index_end]:
            index_start=index_start-1
            index_end=index_end+1
        if max_length<index_end-index_start+1:
            max_length=index_end-index_start+1
            max_index=index
        if index+1!=l and str_list[index+1]==str_list[index]:
            index_start=index
            index_end=index+1
            while index_start!=0 and index_end!=l and str_list[index_start]==str_list[index_end]:
                index_end=index_end+1
                index_start=index_start-1
            if max_length<index_end-index_start+1:
                max_length=index_end-index_start+1
                max_index=[index_start,index_end]
        index=index+1
    return max_index,max_length

#test46
print len(list(func(num=6, state=())))

#test48
#print searchNumInArr(432165,[6,5,4,3,2,1])

#test58
#reversePrint(n6)

#test61
#print findNumAppearOnce([1,3,3,1,2,4])

#test62
#n1=LinkedNode.LinkedNode(None,1)
#n2=LinkedNode.LinkedNode(n1,2)
#n3=LinkedNode.LinkedNode(n2,3)
#n4=LinkedNode.LinkedNode(n3,4)
#n5=LinkedNode.LinkedNode(n4,5)
#n6=LinkedNode.LinkedNode(n5,6)
#n8=LinkedNode.LinkedNode(None,8)
#n7=LinkedNode.LinkedNode(n8,7)
#print findFirstCommonNodeInNotCycleList(n6,n7)

#test63
#print deleteChar("They are students","aeiou")

#test 64
#print findUnlyNum(10)

#test65
#print list(outputMaxNDigits(4))

#test66
#l1=[1,2,3]
#reverseStack(l1,[])
#print l1

#print generateMinInteger([321,34,12],tag=True)
#print exponent(2.3,3)
#print 2.3**3

#test 73
print maxMirrorSubStringLength("gogle")
